AI Exam (OLD)

Here we just need to basically draw an automaton with edges that have a cost.
The cost will be the heuristic which is just the shortest number of blocks that can be traveled to reach the exit.

Here, in addition to the cost, the prof has included the direction that the edge takes us to.

We just add to the "reached" set the node in the "frontier" that has the lowest cost.

In the squares above:

• Top-left: state
• Top-right: actual cost to reach
• Bottom-left: step at which they are added to "frontier"
• Bottom-right: step in which they are added to "reached"

A heuristic function is said to be admissible if it never overestimates the cost of reaching the goal. Also it must have a value for every input.